﻿#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <iterator>
#include "grafy.h"
#pragma warning( disable : 4290 )

bool porownanie(E i, E j) {return i.wart_drogi<j.wart_drogi; }
bool operator ==( const node & d, const int & v ){return d.wierzcholek==v;}
bool operator ==( const E & d, const int & v ){return d.nr_wezla==v;}


///MACIERZ WAG
void grafm::adde(unsigned x, unsigned y,unsigned waga) throw(string)
{
        if(mac.size()>y&&mac.size()>x)
        {
                mac[x][y]=waga;
                mac[y][x]=waga;
        }
        else
        {
                string wyj="dodawanie krawadzie pomiedzy nieistniejacymi wierzcholkami";
                throw wyj;
        }
        this->counte();
}
void grafm::dele(unsigned x, unsigned y, bool all) throw(string)//TODO all !!s
{

        if(mac.size()>y&&mac.size()>x)
        {
                if(mac[x][y]>0) mac[x][y]--;
                if(mac[y][x]>0) mac[y][x]--;
        }
        else
        {
                string wyj="dele:out of index\n";
                throw wyj;
        }
        this->counte();
}
void grafm::addv(uint iledodac)
{
	for(uint kolejnyV=0;kolejnyV<iledodac;kolejnyV++)
	{
        for(unsigned i=0;i<mac.size();i++)mac[i].push_back(0);
        v++;
        vector <unsigned> empty(v,0);
        mac.push_back(empty);
	}        
}

void grafm::delv()//ostani v usuwa
{
        for(unsigned i=0;i<mac.size();i++)mac[i].pop_back();
        v--;
        mac.pop_back();
}
void grafm::delv(unsigned x) throw(string)
{
        if(mac.size()<x)
        {
                string wyj="usuwanie v ktorego nie ma";
                throw wyj;
        }
        else
        {
                for(unsigned i=0;i<mac.size();i++)
                {
                        mac[i].erase(mac[i].begin()+x);
                }
                mac.erase(mac.begin()+x);
                v--;
        }
}
void grafm::show()
{
        for(unsigned i=0;i<mac.size();++i)
        {
                for(unsigned j=0;j<mac.size();++j)
                {
                        cout<<mac[i][j]<<" ";
                }
                cout<<"\n";
        }
}
uint grafm::counte()
{
        e=0;
        for(unsigned i=0;i<mac.size();i++)
        {
                for(unsigned j=0;j<mac.size();j++)
                {
                        if(mac[i][j]!=0)e++;
                }
        }
        e/=2;
        return e;
}
void grafm::fillrand()
{
        srand(time(NULL));
        for(unsigned i=0;i<mac.size();i++)
        {
                for(unsigned j=0;j<mac.size();j++)
                {
                        mac[i][j]=rand()%9;
						mac[j][i]=mac[i][j];
                        if(i==j)mac[i][j]=0;
                }
				mac[i][0]=0;
				mac[0][i]=0;
        }
}
void grafm::make_sym()
{
        for(unsigned i=0;i<v;i++)
        {
                for(unsigned j=0;j<v;j++)
                {
                       mac[j][i]=mac[i][j];                   
					// mac[j][i]=0;
                }
        }
}
void grafm::loadsample()
{
	addv(7);
	adde(1,2,5);
	adde(1,3,3);
	adde(1,4,4);
	adde(1,5,8);
	adde(2,4,4);
	adde(2,6,8);
	adde(3,5,5);
	adde(4,6,9);
	cout<<"zaladowano przykladowy graf"<<endl;
}
void grafm::loadsample1()
{
	addv(6);
	adde(1,2,3);
	adde(1,3,6);
	adde(1,4,4);
	adde(1,5,7);
	adde(2,3,2);
	adde(3,4,6);
	adde(3,5,3);
	adde(4,5,8);
	cout<<"zaladowano przykladowy graf"<<endl;
}
grafm::grafm(uint vv):graf(vv),skierowany(false)
{
        vector <unsigned> empty(v,0);
        for(unsigned i=0;i<v;i++)
        {
                mac.push_back(empty);
        }
}

grafm::grafm(grafm &old_grafm)
{
    v=old_grafm.getv();
    e=old_grafm.gete();
    skierowany=old_grafm.skierowany;
    mac=old_grafm.mac;
}
bool minfn(uint i,uint j)
{
	if(i<j && i!=0)return true;
	if(i>=j && j!=0)return false;
}

uint grafm::prim(int start)
{
	uint mst=0;
	vector <vector<unsigned>> macb;
	macb=mac;//backup mac;
	vector<uint>::iterator imin,tmp1,tmp2;
	int oldimin;//helper
	vector<int>zuzyte;
	int nextV=999;//dunno
	int mini;//indeks najmnieszego v
	int dodacdomst=0;

		zuzyte.push_back(start);//z którego
		oldimin=*min_element(macb[start].begin(),macb[start].end());//int min waga?
		for(int ileV=1;ileV<macb.size()-1;ileV++)//care
		{
			oldimin=*min_element(macb[ileV].begin(),macb[ileV].end(),minfn);//here
			for(int i=0;i<zuzyte.size();i++)
			{
				imin=min_element(macb[zuzyte[i]].begin(),macb[zuzyte[i]].end(),minfn);//waga min
				mini=distance(macb[zuzyte[i]].begin(),imin);//wierzcholek do ktorego waga min
				if(zuzyte.size()==1)dodacdomst=*imin;
 				if(oldimin>=*imin && mini!=0)
				{
					nextV=mini;
					oldimin=*imin;
					dodacdomst=*imin;
				}
			}			
			zuzyte.push_back(nextV);
			//mst+=*imin;			
			mst+=dodacdomst;

			int wtf=zuzyte.at(distance(zuzyte.begin(),zuzyte.end())-2);//indeks pomiedzy ktorymi usuwac
			//usuwanie zuuzytych krawedzi
			macb.at(wtf).at(nextV)=0; 
			macb.at(nextV).at(wtf)=0;	

			macb.at(start).at(nextV)=0; 
			macb.at(nextV).at(start)=0;
		}
	
 	return mst;
}

/*
prim:


getfirstV

connect z najblizszym wierzcholkiem
	{
		dla danych wierzcholków find min krawedz
		add waga to mst
		add do nowego podgrafu
	}	

podgraf = lista wierzchołków mst
az do konca
zwrócić cały graf
*/

uint grafm::kruskal()
{
	uint mst=0;
	vector <int> color;
	for(int i=0;i<this->getv();++i)
	{
		color.push_back(i);
	}

	vector<uint>::iterator imin;//najmniejsza waga w grafie
	vector<uint> min_list;//wektor najmnieszych z wierzcholkow
	vector<uint> pokolorowane;
	uint v1,v2;//ktore v do pokolorowania
	vector <vector<unsigned>> macb;
	macb=mac;

	
	for(int i=0;i<macb.size();i++)
		{
			min_list.push_back(*min_element(macb.at(i).begin(),macb.at(i).end(),minfn));
		}

	for(int krok=0;krok<macb.size()-2;krok++)
	{
		for(int i=0;i<macb.size();i++)
		{
			min_list[i]=(*min_element(macb.at(i).begin(),macb.at(i).end(),minfn));
		}
		imin=min_element(min_list.begin(),min_list.end(),minfn);//or here
		
		for(int i=0;i<min_list.size();i++)
		{
			for(int j=0;j<min_list.size();j++)
			{
				if(min_list[i]==*imin && min_list[j]==*imin && i!=j && (color[i]!=color[j]))
				{
					v1=i;
					v2=j;	
				}
			}
		}
		//znaleziono v1 i v2 do pokolorowania
		pokolorowane.push_back(v2);
		pokolorowane.push_back(v1);

		int tmp=color[v2];
		for(int v=0;v<macb.size();v++)
		{
			if(color[v]==tmp)
			{
				color[v]=color[v1];

			}
		}//pokolorowanie all na ten sam kolor;

		macb[v1][v2]=0;
		macb[v2][v1]=0;	

		//jezeli 2 dowolne maja ten sam kolor to delete
		for(int i=0;i<this->getv();i++)
		{
			for(int j=0;j<this->getv();j++)
			{
				if(color[i]==color[j])
				{
					macb[i][j]=0;
					macb[j][i]=0;
				}
			}
		}
		
		mst+=*imin;
	}
return mst;
}
/*
kruskal:

check spójność()//brak wiszących w powietrzy krawędzi i wierzchołków
check CzyNieskierowany()//musi być symetryczny po prostu


color all na inny kolor
	{
	find najmnieszy kraw w calym
	connect V (but check czy ten sam kolor)
	make sam color
	do it again
	}
*/

///LISTA KRAWEDZI
//wierzcholek wierzcholek waga
 ostream & operator<< (ostream &wyjscie,const kraw &k) //kraw <<        
 {
	 return wyjscie  <<k.vz  << "  " <<k.vdo<<"  "<<k.waga<<endl;
 }
 ///LISTA KRAWEDZI
uint grafl::counte()
{ 
	return mac.size();
}
uint grafl::getv()
{
	uint ilev=0;
	for(uint i=0;i<999;i++)//stały max,care
	{
		for(uint indeks_mac=0;indeks_mac<mac.size();indeks_mac++)
		{
				if(mac.at(indeks_mac).vz==i||mac.at(indeks_mac).vdo==i)
				{
					ilev++;
					++i;
				}
		}
	}
	this->v=ilev;
	return ilev;
}
void grafl::adde(uint vz,uint vdo, uint waga)
{
	kraw temp(vz,vdo,waga);
	mac.push_back(temp);
}
void grafl::dele(uint VZ,uint VDO)
{
	for(int i=0;i<mac.size();i++)
	{
		if((mac.at(i).vz==VZ && mac.at(i).vdo==VDO)||(mac.at(i).vz==VDO && mac.at(i).vdo==VZ))
		{
			if(mac.size()>i)mac.erase(mac.begin()+i);
		}
	}
}
void grafl::show()
{
	for(uint i=0;i<mac.size();i++)
	{
		cout<<mac.at(i);
	}
}
void grafl::fillrand()
{
	srand(time(NULL));
	kraw empty(1,2,1);
	for(uint i=0;i<mac.size();i++)
	{
		mac.push_back(empty);
		empty.vz=rand()%mac.size() +1;
		empty.vdo=rand()%mac.size() +1;
	}
	e=this->counte();
}
grafl::grafl(uint vv):graf(vv)
{

	e=this->counte();
}
grafl::grafl(grafl &old_graf)
{
    v=old_graf.getv();
    e=old_graf.gete();
	mac=old_graf.mac;
}

void grafl::loadsample()
{
	adde(1,2,5);
	adde(1,3,3);
	adde(1,4,4);
	adde(1,5,8);
	adde(2,4,4);
	adde(2,6,8);
	adde(3,5,5);
	adde(4,6,9);
	cout<<"zaladowano przykladowy graf"<<endl;
}

int grafl::FindMinWagaZ(uint v,uint &dokad)
{
	int min=9999;
	bool inside=0;
	for(int i=0;i<mac.size();i++)
	{
		if((mac.at(i).vz==v||mac.at(i).vdo==v )&&mac.at(i).waga<min)
		{
			inside=1;
			min=mac.at(i).waga;
			if(mac.at(i).vz==v)dokad=mac.at(i).vdo;
			else dokad=mac.at(i).vz;
		}
	}
	if(inside==0)return 0;
	return min;
}
bool operator ==( const kraw & d, const kraw & v ){return d.waga==v.waga;}
bool operator <( const kraw & d, const kraw & v ){return d.waga<v.waga;}
uint grafl::prim(int start)
{
	uint mst=0;
	vector <kraw> macb;//backup
	macb=mac;//backup mac;
	vector<uint>::iterator imin,tmp1,tmp2;
	int oldimin;//helper
	vector<int>zuzyte;//z których wierzchołków szukać drogi
	//int nextV=0;//dunno
	int mini;//indeks najmnieszego v
	uint dokad,skad;
	int minWaga=999;

		zuzyte.push_back(start);//z którego
		//oldimin=*min_element(macb.begin(),macb.end());//najmniejsza waga dla wierzcholka start
		oldimin=this->FindMinWagaZ(start,dokad);

		for(int ileV=1;ileV<macb.size()-1;ileV++)
		{
			//oldimin=*min_element(macb[ileV].begin(),macb[ileV].end(),minfn);//here
			oldimin=this->FindMinWagaZ(ileV,dokad);
			for(int i=0;i<zuzyte.size();i++)
			{				
				minWaga=this->FindMinWagaZ(zuzyte[i],dokad);
				skad=zuzyte[i];
				if(oldimin>=minWaga)
				{
					//nextV=i;
					
					oldimin=minWaga;
				}

			}			
			if(find(zuzyte.begin(),zuzyte.end(),dokad)==zuzyte.end())//zapobieganie cyklom
			{
				zuzyte.push_back(dokad);
				mst+=minWaga;			
				//int wtf=zuzyte.at(distance(zuzyte.begin(),zuzyte.end())-2);//indeks pomiedzy ktorymi usuwac
				//usuwanie zuuzytych krawedzi
				
				//macb.at(wtf).at(mini)=0; 
				//macb.at(mini).at(wtf)=0;	
			}
			
			this->dele(dokad,zuzyte.back());
			//this->dele(dokad,zuzyte.at(ileV-1));
			this->dele(dokad,skad);
			this->dele(start,skad);
		}
	
 	return mst;
}
uint grafl::kruskal()
{
uint mst=0;
	vector <int> color;
	for(int i=0;i<=this->getv()+1;i++)
	{
		color.push_back(i);
	}

	vector<kraw>::iterator imin;//najmniejsza kraw w grafie
	vector<uint> pokolorowane;
	uint v1,v2;//ktore v do pokolorowania
	
	int i,j;

	for(int krok=0;krok<color.size()-1;krok++)
	{		
		imin=min_element(mac.begin(),mac.end());		
		i=(*imin).vdo;
		j=(*imin).vz;
		if(i!=j && (color[i]!=color[j]))
			{
				v1=i;
				v2=j;		
				pokolorowane.push_back(v2);
				pokolorowane.push_back(v1);

				int tmp=color[v2];
				for(int v=0;v<getv();v++)
				{
					if(color[v]==tmp)
					{
						color[v]=color[v1];
					}
				}	
				mst+=(*imin).waga;			
			}
		mac.erase(imin);
		for(int i=0;i<this->getv();i++)
		{
			for(int j=0;j<this->getv();j++)
			{
				if(color[i]==color[j])
				{
					this->dele(i,j);
				}
			}
		}
	}
return mst;
}
void grafl::loadsampleD()
{		
		this->adde(1,2,5);
		this->adde(1,3,3);
		this->adde(1,4,4);
		this->adde(1,5,8);
		this->adde(1,6,12);
		this->adde(2,1,3);
		this->adde(2,6,7);
		this->adde(3,1,3);
		this->adde(3,5,4);
		this->adde(4,2,4);
		this->adde(5,6,2);	
		cout<<"załadowano przykładowy graf\n";
}
int grafl::getw(uint VZ,uint VDO)
{
for(int i=0;i<mac.size();i++)
	{
		if((mac.at(i).vz==VZ && mac.at(i).vdo==VDO)||(mac.at(i).vz==VDO && mac.at(i).vdo==VZ))
		{
			return mac.at(i).waga;
		}
	}

}
int grafl::djikstra(uint Z,uint DO)
{
	int testV=getv()+2;
vector<E> pol(testV);//made vecotr
vector<E> found;

pol[Z].wart_drogi=0;
pol[Z].nr_wezla=Z;
pol[Z].poprzednik=Z;

vector<node>::iterator it;
vector<E>::iterator min,actual;

for(int i=Z+1;i<testV;i++)
{	
	//it=find(lista[Z].begin(),lista[Z].end(),i);
	
	//pol[i].wart_drogi=it->waga;
	pol[i].wart_drogi=this->getw(Z,i);
	pol[i].nr_wezla=i;
	pol[i].poprzednik=Z;
}//polaczenie Z
min=min_element(pol.begin()+1,pol.end(),porownanie);
found.push_back(*min);
pol.erase(min);
//polaczenia z Z done
for(int krok=0;krok<mac.size()-2;krok++)
{
	for(int i=1;i<pol.size();i++)
	{	
		int doktorego=pol.at(i).nr_wezla;//szukamy drogi dla tego wezla
		int zktorego=found[krok].nr_wezla;
		int tempdroga=0;

		tempdroga=this->getw(zktorego,doktorego);
		tempdroga+=found[krok].wart_drogi;

		if(tempdroga<pol[i].wart_drogi)
		{
			//cout<<"znaleziono mniejsza droge z "<<zktorego<<" do " <<doktorego<<"wart: "<<tempdroga<<endl;
			pol[i].wart_drogi=tempdroga;
			pol[i].poprzednik=zktorego;
		}
	}

min=min_element(pol.begin()+1,pol.end(),porownanie);
if(pol.size()>1)
	{
	found.push_back(*min);
	pol.erase(min);
	}
}
//obliczanie najkrotszej drogi
int najkrotszadroga=0;
int tempV;
vector<E>::iterator eit;
vector<int> mindrogaV;

eit=find(found.begin(),found.end(),DO);
//for(int i=0;i<found.size()-2;i++)
{
	najkrotszadroga+=eit->wart_drogi;
	mindrogaV.push_back(eit->nr_wezla);
	tempV=eit->poprzednik;
	eit=find(found.begin(),found.end(),tempV);
}

cout<<"najkrosza droga dijkstry: "<<najkrotszadroga<<endl;
return najkrotszadroga;
}

int grafl::bell(uint Z)
{
	//this->countv();
//	int V = this->getv();
	int V=7;
	int E = mac.size();
    vector<int> dist(V,999);

    dist[Z] = 0;
 
    for (int i = 1; i <= V-1; i++)
    {
		for (int j = 0; j < E; j++)
        {
			int u = mac.at(j).vz;
			int v = mac.at(j).vdo;
            int weight = mac.at(j).waga;

            if (dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

	printf("V  \t Odleglosc od zrodla\n");
    for (int i = 1; i < V; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
	return 0;
}

///LISTA SĄSIADOW
int grafs::FindMinWagaZ(uint v,uint &dokad)
{
	int min=9999;
//	for(int i=0;i<lista.size();i++)
	//{
	//	if((mac.at(i).vz==v||mac.at(i).vdo==v )&&mac.at(i).waga<min)
	//	{
	//		min=mac.at(i).waga;
	//		if(mac.at(i).vz==v)dokad=mac.at(i).vdo;
	//		else dokad=mac.at(i).vz;
		//}
	//}
	return min;
}
grafs::grafs(grafs &old_graf)
{
	v=old_graf.getv();
    e=old_graf.gete();
	lista=old_graf.lista;
}
grafs::grafs(uint ilev,bool full):graf(ilev)//warning: nieczytelny kod w tej metodzie
{
	node start(9,9);
	v=ilev;
	vector <node> first;//genialna przestrzen nazw,fuck
	first.push_back(start);
	srand(time(NULL));
	if(full)
	{

		for(int i=0;i<ilev;++i)
		{
		
			lista.push_back(first);
			start.wierzcholek=rand()%ilev+1;
			first.at(0)=start;// lool
		}
	}
	else 
	{
		start.waga=0;
		start.wierzcholek=0;
		for(int i=0;i<ilev;++i)
		{		
			lista.push_back(first);
		}
	}
		
}

void grafs::show()
{
	cout<<"V -[Vdo,Waga][Vdo,Waga]"<<endl;
	for(int ivec=0;ivec<lista.size();++ivec)//iterator vector
	{
		cout<<ivec<<" - ";
		for(int ilist=0;ilist<lista.at(ivec).size();++ilist)//iter listy, well vectora w srodku juz
		{
			cout<<"["
				<<lista.at(ivec).at(ilist).wierzcholek<<","
				<<lista.at(ivec).at(ilist).waga
				<<"]";
		}
		cout<<endl;
	}
}
void grafs::adde(uint vz,uint vdo,uint waga)//nie sprawdza poprawnosci danych
{
	//sprawdzanie poprawnosci- czy vz i czy vdo istnieja TODO

	node temp(vdo,waga);
	if(vdo>lista.size()||vz>lista.size())
	{
		cout<<"trzeba stworzyc nowy wierzcholek"<<endl;
		//lista.push_back(temp);
	}
	else lista.at(vz).push_back(temp);
}
void grafs::dele(uint vz,uint vdo)
{
	for(uint i=0;i<lista.at(vz).size();++i)
	{
		if(lista.at(vz).at(i).wierzcholek==vdo)
		{
			lista.at(vz).erase(lista.at(vz).begin()+i);
		}
	}
}
int grafs::getw(uint vz,uint vdo)
{
	for(uint i=0;i<lista.at(vz).size();++i)
	{
		if(lista.at(vz).at(i).wierzcholek==vdo)
		{
			return lista.at(vz).at(i).waga;
		}
	}
	return 9999;
}
void grafs::loadsampleD()
{		
		this->adde(1,2,5);
		this->adde(1,3,3);
		this->adde(1,4,4);
		this->adde(1,5,8);
		this->adde(1,6,12);
		this->adde(2,1,3);
		this->adde(2,6,7);
		this->adde(3,1,3);
		this->adde(3,5,4);
		this->adde(4,2,4);
		this->adde(5,6,2);	
		cout<<"załadowano przykładowy graf\n";
}
void grafs::loadsample()
{		
		adde(1,2,5);
		adde(2,1,5);
		adde(1,3,3);
		adde(3,1,3);
		adde(1,4,4);
		adde(4,1,4);
		adde(1,5,8);
		adde(5,1,8);
		adde(2,4,4);
		adde(4,2,4);
		adde(2,6,8);
		adde(6,2,8);
		adde(3,5,5);
		adde(5,3,5);
		adde(4,6,9);
		adde(6,4,9);
		cout<<"załadowano przykładowy graf\n";
}
bool operator <( const node & d, const node & v ){return d.waga<v.waga;}
//bool operator ==( const node & d, const node & v ){return d.waga==v.waga;}
uint grafs::prim()
{
	uint mst=0;

	return mst;
}
uint grafs::kruskal()
{
uint mst=0;
vector <int> color;

	for(int i=0;i<this->getv();++i)
	{
		color.push_back(i);
	}

	vector<node>::iterator imin;//najmniejsza waga w grafie
	vector<node> min_list;//wektor najmnieszych z wierzcholkow
 	vector<uint> pokolorowane;
	uint v1,v2;//ktore v do pokolorowania
	
	for(int i=0;i<lista.size();i++)
	{
		min_list.push_back(*min_element(lista.at(i).begin(),lista.at(i).end()));
	}

	for(int krok=0;krok<lista.size()-2;krok++)
	{
	//	for(int i=0;i<lista.size();i++)
		{
	//		min_list[i]=(*min_element(mac.at(i).begin(),mac.at(i).end(),minfn));
		}
		imin=min_element(min_list.begin(),min_list.end());//or here
	//	
		for(int i=0;i<min_list.size();i++)
		{
			for(int j=0;j<min_list.size();j++)
			{
				if(min_list[i]==*imin && min_list[j]==*imin && i!=j && (color[i]!=color[j]))
				{
					v1=i;
					v2=j;	
				}
			}
		}
	//	//znaleziono v1 i v2 do pokolorowania
		pokolorowane.push_back(v2);
		pokolorowane.push_back(v1);

		int tmp=color[v2];
		for(int v=0;v<lista.size();v++)
		{
			if(color[v]==tmp)
			{
				color[v]=color[v1];

			}
		}//pokolorowanie all na ten sam kolor;

		//safe valve, usuwa cykle
		mst+=(*imin).waga;
		//if(lista.size()>v1)
			this->dele(v1,v2);
		//if(lista.size()>v2)
			this->dele(v2,v1);
	}
return mst;
}


int grafs::djikstra(uint Z,uint DO)
{
int testV=getv();
vector<E> pol(testV);//made vecotr
vector<E> found;

pol[Z].wart_drogi=0;
pol[Z].nr_wezla=Z;
pol[Z].poprzednik=Z;

vector<node>::iterator it;
vector<E>::iterator min,actual;

for(int i=2;i<testV;i++)
{	
	it=find(lista[Z].begin(),lista[Z].end(),i);
	
	pol[i].wart_drogi=it->waga;
	pol[i].nr_wezla=i;
	pol[i].poprzednik=Z;
}
min=min_element(pol.begin()+1,pol.end(),porownanie);
found.push_back(*min);
pol.erase(min);
//polaczenia z Z done
for(int krok=0;krok<lista.size()-2;krok++)
{
	for(int i=1;i<pol.size();i++)
	{	
		int doktorego=pol.at(i).nr_wezla;//szukamy drogi dla tego wezla
		int zktorego=found[krok].nr_wezla;
		int tempdroga=0;

		tempdroga=this->getw(zktorego,doktorego);
		tempdroga+=found[krok].wart_drogi;

		if(tempdroga<pol[i].wart_drogi)
		{
			//cout<<"znaleziono mniejsza droge z "<<zktorego<<" do " <<doktorego<<"wart: "<<tempdroga<<endl;
			pol[i].wart_drogi=tempdroga;
			pol[i].poprzednik=zktorego;
		}
	}

min=min_element(pol.begin()+1,pol.end(),porownanie);
found.push_back(*min);
pol.erase(min);
}
//obliczanie najkrotszej drogi
int najkrotszadroga=0;
int tempV;
vector<E>::iterator eit;
vector<int> mindrogaV;

eit=find(found.begin(),found.end(),DO);
//for(int i=0;i<found.size()-2;i++)
{
	najkrotszadroga+=eit->wart_drogi;
	mindrogaV.push_back(eit->nr_wezla);
	tempV=eit->poprzednik;
	eit=find(found.begin(),found.end(),tempV);
}

cout<<"najkrosza droga dijkstry: "<<najkrotszadroga<<endl;
return najkrotszadroga;
}
int grafs::bell(uint Z)
{
	int V = this->getv();
	int E = 10;
    vector<int> dist(V,999);

    dist[Z] = 0;
 
    for (int i = 1; i <= V-1; i++)
    {
		for (int j = 1; j < lista[i].size(); j++)
        {
			int u = i;
			int v = lista[i][j].wierzcholek;
            int weight = lista[i][j].waga;

            if (dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

	printf("V   Odleglosc od zrodla\n");
    for (int i = 1; i < V; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
	return 0;
}

///POŁĄCZONA LISTA
element* lista::push_back(uint Vdo,uint Waga)
{
	element* p=new element(Vdo,Waga);
	//p->vdo=Vdo;
	//p->waga=Waga;
	if(last) last->next=p;//jeśli wskaznik na ostatni element istnieje to wskaznik(next) w tym elemencie = nastepny element
	p->next = NULL;
	last=p;//ostatni element na liscie to p
	if(!first) first=last;//jesli nie ma first to first =last
	ilosc++;
	return last;
}

element* lista::search(uint vdo)//zwraca poprzedni wskaznik
{
	element* poprzedni=first;
	element* p;
	p=first->next;
	if(vdo==first->vdo)
	{
		string wyj="search znalazl pierwszy element a tak to nie dziala";
		throw wyj;
		return NULL;
	}
	else
	{
		for(int i=0;i<ilosc;i++)
		{
			if(p->vdo==vdo) return poprzedni;
			poprzedni=poprzedni->next;
			if(p->next)p=p->next;
		}	
	}
	string wyj="search nie znalazl elementu";
	throw wyj;
	return NULL;
}

void lista::del(uint ktory)
{
	if(ilosc)
	{
		element* p;
		p=search(ktory);//wskaznik na poprzedni element

		p->next=p->next->next;
		if(!(p->next))last=p;
		ilosc--;
	}
}

uint lista::getw(uint ktory)
{
	if(ilosc)
	{
		element* p;
		p=search(ktory);//wskaznik na poprzedni element	
		return p->waga;
	}
}
element* lista::index(uint n)//jak tablica indeksy [0][1][2][.]
{
	element *p;
	p=first;
	
	for(int i=0;i<n;i++)
	{
		p=p->next;
	}
	return p;
}

void lista::show()
{
	element *p;
	p=first;
	if(ilosc==0)cout<<"lista pusta\n";
	cout<<"[VDO] \t waga"<<endl;
	for(int i=0;i<this->getsize();++i)
	{
		p->show();
		p=p->next;
	}
}
lista::~lista()
{
	element* p;
	while(first)
	{
		p=first->next;
		delete first;
		first=p;
	}
}
//-----------------------------------------
void grafp::addv()
{
	lista lis;
	tab.push_back(lis);
}
void grafp::adde(uint vz, uint vdo,uint waga)
{
	tab[vz].push_back(vdo,waga);
}

void grafp::show()
{
	for(int i=0;i<tab.size();i++)
	{
		tab[i].show();
	}
}
void grafp::delv(uint ktory)
{
	if(!ktory)//del ost
	{
		tab.erase(tab.end());
	}
	else//del ktory
	{
		tab.erase(tab.begin()+ktory);
	}
}
void grafp::dele(uint vz,uint vdo)
{
	tab[vz].del(vdo);
}
grafp::grafp(uint ilev)
{
	lista lis;
	for(int i=0;i<ilev;i++)
	{
		tab.push_back(lis);
	}
}
uint grafp::getw(uint vz,uint vdo)
{
	return tab[vz].getw(vdo);
}
///INNE
